/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 *
 */
public class InterleavingString {

	/**
	Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

	For example,
	Given:
	s1 = "aabcc",
	s2 = "dbbca",

	When s3 = "aadbbcbcac", return true.
	When s3 = "aadbbbaccc", return false.
	 */
	/*
	best
	match[i1][i2] means that s1[i1 - 1] and s2[i2 - 1] match s3[i1 + i2 + 1]
	*/
	public boolean isInterleave(String s1, String s2, String s3) {
		if (s1 == null || s2 == null || s3 == null)
			return false;

		if (s1.length() + s2.length() != s3.length())
			return false;

		boolean match[][] = new boolean[s1.length() + 1][s2.length() + 1];
		match[0][0] = true;
		for (int i = 1; i < s2.length() + 1; i++) {
			if (match[0][i - 1] && s2.charAt(i - 1) == s3.charAt(i - 1))
				match[0][i] = true;
		}

		for (int i = 1; i < s1.length() + 1; i++) {
			if (match[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1))
				match[i][0] = true;
		}

		for (int i1 = 1; i1 < s1.length() + 1; i1++) {
			for (int i2 = 1; i2 < s2.length() + 1; i2++) {
				if ((match[i1 - 1][i2] && s1.charAt(i1 - 1) == s3.charAt(i1
				        + i2 - 1))
				        || (match[i1][i2 - 1] && s2.charAt(i2 - 1) == s3
				                .charAt(i1 + i2 - 1)))
					match[i1][i2] = true;

			}
		}

		return match[s1.length()][s2.length()];
	}

	public boolean isInterleave2(String s1, String s2, String s3) {
		if (s1 == null || s2 == null || s3 == null)
			return false;
		if (s1.length() + s2.length() != s3.length())
			return false;
		boolean[] match = new boolean[s2.length() + 1];

		for (int i1 = 0; i1 <= s1.length(); i1++) {
			for (int i2 = 0; i2 <= s2.length(); i2++) {
				if (i1 == 0 && i2 == 0)
					match[0] = true;
				else if (i1 == 0) {
					match[i2] = match[i2 - 1]
					        && s2.charAt(i2 - 1) == s3.charAt(i2 - 1);
				} else if (i2 == 0) {
					match[0] = match[0]
					        && s1.charAt(i1 - 1) == s3.charAt(i1 - 1);
				} else
					match[i2] = match[i2 - 1]
					        && s2.charAt(i2 - 1) == s3.charAt(i1 + i2 - 1)
					        || match[i2]
					        && s1.charAt(i1 - 1) == s3.charAt(i1 + i2 - 1);

			}
		}

		return match[s2.length()];
	}

	/**
	 * 
	 */
	public InterleavingString() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		InterleavingString is = new InterleavingString();
		String s1 = "a";
		String s2 = "";
		String s3 = "c";
		System.out.println(is.isInterleave2(s1, s2, s3));
	}

}
